/**
 * Copyright (C) 2008 Christopher Allen Ogden
 *
 *     This file is part of Odysi.
 *
 *  Odysi is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  Odysi is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Odysi.  If not, see <http://www.gnu.org/licenses/>.
 */

#pragma once
#ifndef NULL
#define NULL 0
#endif
#define LARGEST_UINT 0xFFFFFFFF

/**
 * Cache system.
 *
 * @author  Ogden, Chris
 */
template <class K, class D>
class Cache
{
    public:
        /**
         * Constructor.
         *
         * @param size  The maximum number of items cached.
         */
        Cache(unsigned int size):_size(size),_curAge(0),_data(new CacheItem[size]) { }

        /**
         * Add an item to the cache.
         *
         * @param key   The key of the item.
         * @param data  The item itself.
         */
        void add(const K &key, D * data)
        {
            __builtin_prefetch(_data);
            // Find the lowest.
            unsigned int lowest = LARGEST_UINT;
            unsigned int lowIndex = 0;
            for (unsigned int i = 0; i < _size; i++) {
                if (_data[i].age < lowest) {
                    lowest = _data[i].age;
                    lowIndex = i;
                }
            }
            
            // Delete the data if needed.
            if (__builtin_expect(_data[lowIndex].data != NULL, true)) {
                delete _data[lowIndex].data;
            }

            // Set the info.
            _data[lowIndex].key = key;
            _data[lowIndex].data = data;
            _data[lowIndex].age = _curAge + _size;
            _curAge++;
            if (__builtin_expect(_curAge == LARGEST_UINT, false)) fixAge();
            return;
        }

        /**
         * Get the address of an item.
         *
         * @param key   The key of the item to get.
         * @return      The address of the item, or NULL if it does not
         *              exist.
         */
        D * get(const K &key)
        {
            __builtin_prefetch(_data);
            for (unsigned int i = 0; i < _size; i++) {
                if (_data[i].data && _data[i].key == key && _data[i].data) {
                    _data[i].age = _curAge + _size;
                    _curAge++;
                    if (__builtin_expect(_curAge == LARGEST_UINT, false)) fixAge();
                    return _data[i].data;
                }
            }
            return NULL;
        }

        /**
         * Clear the cache.
         */
        void clear(void)
        {
            for (unsigned int i = 0; i < _size; i++) {
                if (_data[i].data) {
                    delete _data[i].data;
                    _data[i].data = NULL;
                }
                _data[i].age = 0;
            }
            _curAge = 0;
        }

        /**
         * Destructor.
         */
        ~Cache()
        {
            clear();
            delete []_data;
        }
    private:
        inline void fixAge(void)
        {
            for (unsigned int i = 0; i < _size; i++) {
                _data[i].age -= (LARGEST_UINT - _size);
            }
        }

        struct CacheItem
        {
            CacheItem():data(NULL),age(0) { }
            K key;
            D * data;
            unsigned int age;
        };

        const unsigned int _size;
        unsigned int _curAge;
        CacheItem *_data;
};
